import java.util.Random;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = new int[]{1,5,1,9,2,4,3,1};
        quickSort(0, nums.length-1, nums);
        for(int e: nums) {
            System.out.print(e + " ");
        }
    }

    public int[] sortArray(int[] nums) {
        /**
         * 排序数组-使用快排进行解决*/
        quickSort(0, nums.length-1, nums);
        return nums;
    }

    public static Random random = new Random();

    public static void quickSort(int left, int right, int[] nums) {
        /**
         * 快速排序递归实现*/
        // 1 递归出口
        if(left >= right) {
            return;
        }

        // 2 找到基准值
        int pivot = partition(left, right, nums);

        // 3 向左右区间递归
        quickSort(left, pivot - 1, nums);
        quickSort(pivot + 1, right, nums);
    }

    public static int partition1(int left, int right, int[] nums) {
        /**
         * 找到基准值，并对数组进行划分*/
        // 1 指定基准值（使用随机值）
        int baseIndex = left + random.nextInt(right - left + 1);
        int baseVal = nums[baseIndex];
        swap(left, baseIndex, nums);
        baseIndex = left;
//        int baseIndex = left;
//        int baseVal = nums[left];

        // 2 根据基准值，对区间进行划分
        while(left < right) {
            while(left < right && nums[right] >= baseVal) {
                right --;
            }
            while(left < right && nums[left] <= baseVal) {
                left ++;
            }
            swap(left, right, nums);
        }

        // 3 找到基准下标
        swap(baseIndex, left, nums);
        return left;
    }

    public static int partition(int left, int right, int[] nums) {
        /**
         * 使用数组分三块的思想对区间进行划分
         * 遇见问题：使用分三块的逻辑超时*/
        // 1 确定基准值
        int baseIndex = left + random.nextInt(right - left + 1);
        int baseVal = nums[baseIndex];

        // 2 分三块
        int l = left - 1;
        int r = right + 1;
        int i = left;
        while(i < r) {
            if(nums[i] < baseVal) {
                // -小于
                swap(i, ++l, nums);
            } else {
                // -若是大于
                while(r > i && nums[i] > baseVal) {
                    swap(i, --r, nums);
                }
                if(nums[i] < baseVal) {
                    swap(i, ++l, nums);
                }
            }
            i++;
        }

        // 3 返回值
        return r-1;
    }

    public static void swap(int a, int b, int[] nums) {
        /**
         * 交换demo*/
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
